2B - The least round way - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef map<ll,ll> mll;
typedef vector<int> vi;
typedef set<ll> sll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
ll gcd(ll a, ll b) {return a == 0? b: gcd(b%a,a);}
ll lcm(ll a, ll b) {return a * (b / gcd(a,b));}
const int inf = 1e5;
#define pb(x) push_back(x)
#define rep(x,n) for (int i = x; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define fo(x) find_by_order(x)
#define ok(x) order_of_key(x)
ll mod = 1e9 + 7;
int MAXN = 100000;
const int d1 = 2, d2 = 5;
int fives[1000][1000], twos[1000][1000], dp_five[1000][1000], dp_two[1000][1000];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    memset(fives,0,sizeof fives);
    memset(twos,0,sizeof twos);
    for (int i = 0; i < 1000; i++) for (int j = 0; j < 1000; j++)
        dp_five[i][j] = dp_two[i][j] = inf;
    vector<vi> grid(n,vi(n));
    bool zero = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            int x = grid[i][j];
            zero |= x == 0;
            if (!x) {
                twos[i][j] = fives[i][j] = inf;
                continue;
            }
            while (!(x & 1)) twos[i][j]++, x >>= 1;
            while (x % d2 == 0) fives[i][j]++, x /= d2;
        }
    }

    dp_two[0][0] = twos[0][0];
    dp_five[0][0] = fives[0][0];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++){
            if (i) {
                dp_two[i][j] = min(dp_two[i][j],twos[i][j] + dp_two[i-1][j]);
                dp_five[i][j] = min(dp_five[i][j],fives[i][j] + dp_five[i-1][j]);
            }
            if (j){
                dp_two[i][j] = min(dp_two[i][j], twos[i][j] + dp_two[i][j-1]);
                dp_five[i][j] = min(dp_five[i][j], fives[i][j] + dp_five[i][j-1]);
            }
        }
    }

    if (min(dp_two[n-1][n-1] , dp_five[n-1][n-1]) >= inf) {
        cout << "1\n";
        rep(0,n-1) cout << "R";
        rep(0,n-1) cout << "D";
        cout << "\n";
        return 0;
    }

    if (min(dp_two[n-1][n-1] , dp_five[n-1][n-1]) > 1 && zero) {
        int pi = -1,pj = -1;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    pi = i; pj = j;
                    break;
                }
            }
            if (pi != -1) break;
        }
        cout << 1 << "\n";
        string ans = "";
        rep(0,pj) ans.pb('R');
        rep(0,pi) ans.pb('D');
        rep(pj,n-1) ans.pb('R');
        rep(pi,n-1) ans.pb('D');
        cout << ans << "\n";
        return 0;
    }

    if (dp_two[n-1][n-1] < dp_five[n-1][n-1]){
        int i = n - 1, j = n - 1;
        string ans = "";
        while (i || j) {
            if (j && dp_two[i][j] == twos[i][j] + dp_two[i][j-1]) ans.pb('R'), j--; 
            else ans.pb('D'), i--;
        }
        reverse(all(ans));
        cout << dp_two[n-1][n-1] << "\n";
        cout << ans << "\n";
    }else {
        int i = n - 1, j = n - 1;
        string ans = "";
        while (i || j) {
            if (j && dp_five[i][j] == fives[i][j] + dp_five[i][j-1]) ans.pb('R'), j--; 
            else ans.pb('D'), i--;
        }
        reverse(all(ans));
        cout << dp_five[n-1][n-1] << "\n";
        cout << ans << "\n";
    }
    //cout << min(min(dp_two[n-1][n-1].first, dp_two[n-1][n-1].second), min(dp_five[n-1][n-1].first, dp_five[n-1][n-1].second));
    return 0;
}